/*
题目: 最大正方形
在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。

https://leetcode.cn/problems/maximal-square/
 */
public class MaximalSquare {
    public int maximalSquare(char[][] matrix) {
        int row = matrix.length;
        int col = matrix[0].length;
        // 表示 以 [i, j] 为右下角时的正方形最大边长
        int[][] dp = new int[row + 1][col + 1];// 防止讨论边界

        int src = 0;
        for (int i = 1; i <= row; i ++) {
            for (int j = 1; j <= col; j ++) {
                if (matrix[i - 1][j - 1] == '1') {
                    dp[i][j] = Math.min(dp[i - 1][j], Math.min(dp[i - 1][j - 1], dp[i][j - 1])) + 1;
                    src = Math.max(src, dp[i][j]);
                } else {
                    dp[i][j] = 0;
                }
            }
        }

        return src * src;
    }
}
